1. Field of the Invention
This invention relates generally to digital transportation networks used in GIS (geographic information system) and navigation applications containing attribute information which describe properties of a point, segment or area of a digital geographic navigation map. More particularly, this invention relates to methods for verifying questionable attributes or filling in missing attributes along segments of a roadway in a digital mapping database.
2. Related Art
Personal navigation devices like that shown for example in FIG. 1 utilize digital maps combined with accurate positioning data from GPS or other data streams. These devices have been developed for commuters seeking navigation assistance, for businesses trying to minimize transportation costs, and many other applications. The effectiveness of such navigation systems are inherently dependent upon the accuracy and completeness of the information provided to it in the form of digital maps and associated attribute data. Likewise, the effectiveness of such navigation systems is also dependent upon accurately and quickly matching the actual, real-world location of the navigation device to a corresponding portion of the digital map. Typically, the navigation system includes a small display screen or graphic user interface that portrays a network of streets as a series of line segments, including a center line running approximately along the center of each street or path, as exemplified in FIG. 1. The traveler can then be generally located on the digital map close to or with regard to that center line. Such GPS-enabled personal navigation devices, such as those manufactured by TomTom N.V. (www.tomtom.com) may be also configured with probe transmitters to generate probe data points. Of course, other suitable devices may be used to generate probe data points including handheld devices, mobile phones, PDAs, and the like.
Digital maps are expensive to produce and update, since exhibiting and processing road information is very costly. Surveying methods or digitizing satellite images have been employed in the past for creating digital maps, but are prone to the introduction of inaccuracies or systematic errors due to faulty or inaccurate input sources or flawed inference procedures. Once a digital map has been created, it is costly to keep map information up to date, since road geometry changes over time.
FIG. 2 illustrates a fractional section of a digital map, in this case a by-directional roadway supporting two-way traffic. A main trunk of the roadway is indicated at 10 and a branch road extending generally perpendicularly from the main trunk 10 is indicated at 12.
It is known, for example, to take probe data inputs from low-cost positioning systems and handheld devices and mobile phones with integrated GPS functionality for the purpose of incrementally learning a map using certain clustering technologies. The input to be processed consists of recorded GPS traces in the form of a standard ASCII stream, which is supported by almost all existing GPS devices. The output is a road map in the form of a directed graph with nodes and edges associated with travel time information. Travelers appropriately fitted with navigation devices may thus produce a trace map in the form of probe data, with nodes created at regular distances. The nodes and edges are stored in a digital map table or database. Through this technique, road geometry can be inferred and the collected probe data points refined by filtering and partitioning algorithms. For a more complete discussion of this technique, reference is made to “Incremental Map Generation with GPS Traces,” Briintrup, R., Edelkamp, S., Jabbar, S., Scholz, B., Proc. 8th Int. IEEE Conf. on Intelligent Transportation Systems, Vienna, Austria, 2005, pages 413-418.
One issue associated with such methods for generating and updating digital maps using probe data relates to certain accuracy issues associated with GPS measurements. As is well known, GPS is based on concepts of satellite ranging, wherein the distances between the GPS receiver and four or more satellites are calculated, as represented illustratively in FIG. 3. Assuming the positions of the satellites 22 are known, the location of the receiver 14 can be calculated by determining the distance from each satellite 22 to the receiver 14. Distance measurements are determined by measuring the amount of time it takes the GPS radio signal 20 to travel from the satellite 22 to the receiver 14. Radio waves travel at the speed of light. Therefore, if the amount of time it takes for the GPS signal to travel from the satellite 22 to the receiver 14 is known, the distance (distance=speed×time) can be determined. Thus, if the exact time when the signal 20 was transmitted and the exact time when it was received or known, the signal's travel time can be easily calculated.
GPS systems are designed to be as nearly accurate as possible, however various factors are known to introduce errors. Added together, these errors cause deviations in the calculated position of the GPS receiver. Several sources for errors are known, some of which include: atmospheric conditions, ephemeris errors, clock drift, measurement noise, selective availability and multi-path. Multi-path error, also know as “urban canyon” error is a serious concern for GPS users. Urban canyon error is caused by a GPS signal 20 bouncing off of a reflective surface prior to reaching the GPS receiver antenna 14. It is difficult to completely correct urban canyon error, even in high precision GPS units. FIG. 4 is a schematic view describing the urban canyon phenomenon. A GPS antenna 14 is stationed between first 16 and second 18 obstacles, which may, for example, represent tall buildings in a city center environment. A GPS signal 20 from one GPS satellite 22 is received without corruption, however a signal 24 from another satellite 26 encounters the first obstacle 16 so that its signal 24 does not proceed directly to the GPS antenna 14. A corrupt signal 24′ from the satellite 26, however, is reflected off the second obstacle 18 and received by the GPS antenna 14. Reflection of the corrupted signal 24′ results in a situation where it takes longer for the signal 24′ to reach the GPS antenna 14 than it should have. This time lag results in a perceived position shift of the GPS antenna 14 from its actual position in real life.
FIG. 5 shows a sample trace path from probe data created by a personal navigation device utilizing the antenna 14. The real, actual position of the moving probe transmitter is represented by the straight line 28 and the calculated position of the GPS antenna 14 is represented by the path 30. As shown, the calculated position of the GPS antenna 14 demonstrates corruption due to the effects of urban canyon lead to gaps or poor quality attribution of segments of the transportation network.
Digital maps can also be derived from satellite imagery, wherein images of roadway networks are digitized and then matched or overlaid with other attribute data to form a digitized transportation network usable by the various navigation devices. However, a similar urban canyon effect can occur when segments of the transportation network are blocked from view, such as from dense tree cover or the like. In such case, attribute information concerning the blocked segments can be all together missing or their accuracy in question or corrupt.
Consequently, digital transportation networks of various types and derived in various ways have numerous segments where there are gaps in attribution such as average speed, posted speed limits, one-way direction indications or position of centerline, among other attributes. This lack of attributes (missing or unreliable) may be a result of drop-outs in the source material that went into making the attribution in the first place, as described above. In a further example, the attribute may be attached to a roadway segment, but one cannot verify its accuracy or precision because the sensor, imagery or other maps from which the attributes are derived cannot themselves be verified as to accuracy. Consequently, metadata associated with accuracy for the given attribute in question would be lower than for surrounding roadway segments where the attribute data does exist and can be verified.
For navigation and other digital mapping systems that rely on extreme accuracy of the attribute information in the database, roadways having segments with missing or poor quality attribute information would be noticed by users of navigation devices, and the software of such devices may also preferentially select alternative routing around these problem segments due to the lack of confidence or absence (gaps) of the attribute information along the affected roadway segments.
To resolve these gaps or inaccuracies of attributes in the database, it is current practice to acquire another source of information to verify the attribution and/or to dispatch field staff to the problem roadway segments in order to ground truth the attributes in question. Both approaches are recognized as being time consuming and costly, but nonetheless presently necessary in order to achieve the desired result of accurate attribution.
It is an object of the present invention to provide a means of filling in attribution information when it is missing, and/or verifying and updating, if necessary, the metadata associated with attribution information to provide high accuracy and precision of attribution for digital transportation roadway network databases, and to do so in a quick, orderly and cost-effective manner.